#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct Node
{
    char s[ 11 ];
    int m;
    Node( ) { }
    Node( char *_s, int _m )
        : m( _m ) { strcpy( s, _s ); }
};

char s[ 11 ];
int n;
queue<Node> q;
bool visit[ 59049 ];

int hash( char *p )
{
    int i, ret = 0;
    for ( i = 0; i < n; i++ )
    {
        ret *= 3;
        switch( p[ i ] )
        {
            case 'r': break;
            case 'g': ret++; break;
            case 'b': ret += 2; break;
        }
    }
    return ret;
}

bool check( char *p )
{
    int i;
    bool flag1 = 1, flag2 = 1, flag3 = 1;
    for ( i = 0; i < n; i++ )
        switch( p[ i ] )
        {
            case 'r': flag2 = flag3 = 0; break;
            case 'g': flag1 = flag3 = 0; break;
            case 'b': flag1 = flag2 = 0; break;
        }
    return flag1 || flag2 || flag3;
}

void work( )
{
    Node p;
    bool flag = false;
    char t[ 11 ];
    int i;
    memset( visit, 0, sizeof( visit ) );
    visit[ hash( s ) ] = 1;
    while ( !q.empty( ) ) q.pop( );
    q.push( Node( s, 0 ) );
    while ( !q.empty( ) )
    {
        p = q.front( ); q.pop( );
        if ( check( p.s ) )
        {
            flag = true;
            break;
        }
        for ( i = 0; i < n - 1; i++ )
        {
            if ( p.s[ i ] != p.s[ i + 1 ] )
            {
                strcpy( t, p.s );
                if ( p.s[ i ] == 'r' )
                    if ( p.s[ i + 1 ] == 'g' )
                        t[ i ] = t[ i + 1 ] = 'b';
                    else
                        t[ i ] = t[ i + 1 ] = 'g';
                if ( p.s[ i ] == 'g' )
                    if ( p.s[ i + 1 ] == 'b' )
                        t[ i ] = t[ i + 1 ] = 'r';
                    else
                        t[ i ] = t[ i + 1 ] = 'b';
                if ( p.s[ i ] == 'b' )
                    if ( p.s[ i + 1 ] == 'r' )
                        t[ i ] = t[ i + 1 ] = 'g';
                    else
                        t[ i ] = t[ i + 1 ] = 'r';
                if ( !visit[ hash( t ) ] )
                {
                    q.push( Node( t, p.m + 1 ) );
                    visit[ hash( t ) ] = 1;
                }
            }
        }
    }
    if ( flag )
        printf("%d\n", p.m);
    else
        printf("No solution!\n");
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%s", s);
        n = strlen( s );
        work( );
    }
    return 0;
}
